public class test01 {
    class Solution {
        public int numSquares(int n) {
            int[] dp = new int[n+1];
            int max = Integer.MAX_VALUE;
            for(int i = 0;i<dp.length;i++){
                dp[i] = max;
            }
            dp[0] = 0;
            //完全背包：正序
            for(int i = 1;i*i<=n;i++){
                for(int j = i*i;j<=n;j++){
                    dp[j] = Math.min(dp[j],dp[j-i*i]+1);
                }
            }
            return dp[n];
        }
    }
}
